//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package 力扣.题库.二分查找;

import java.util.Arrays;

public class demo_1170 {
    public demo_1170() {
    }

    public static void main(String[] args) {
        String[] queries = new String[]{"bbb", "cc"};
        String[] words = new String[]{"a", "aa", "aaa", "aaaa"};
        int[] nums = numSmallerByFrequency(queries, words);
        System.out.println(Arrays.toString(nums));
    }

    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] queriesNum = f(queries);
        int[] wordsNum = f(words);
        Arrays.sort(wordsNum);
        int[] out = new int[queries.length];

        for(int i = 0; i < queriesNum.length; ++i) {
            int l = 0;
            int r = wordsNum.length - 1;

            while(l <= r) {
                int mid = l + (r - l) / 2;
                if (queriesNum[i] < wordsNum[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            out[i] = wordsNum.length - l;
        }

        return out;
    }

    public static int[] f(String[] strs) {
        int[] nums = new int[strs.length];

        for(int i = 0; i < strs.length; ++i) {
            char[] chars = strs[i].toCharArray();
            char min = chars[0];

            for(int j = 1; j < chars.length; ++j) {
                if (chars[j] < min) {
                    min = chars[j];
                }
            }

            int count = 0;

            for(char aChar : chars) {
                if (aChar == min) {
                    ++count;
                }
            }

            nums[i] = count;
        }

        return nums;
    }
}
